Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

  1. Insert a character

  2. Delete a character

  3. Replace a character

Solution:

  1. public class Solution {
  2.   public int minDistance(String word1, String word2) {
  3.     int n1 = word1.length(), n2 = word2.length();
  5.     int[][] dp = new int[n1 + 1][n2 + 1];
  7.     for (int j = 1; j <= n2; j++) {
  8.       dp[0][j] = j;
  9.     }
  11.     for (int i = 1; i <= n1; i++) {
  12.       dp[i][0] = i;
  13.     }
  15.     for (int i = 1; i <= n1; i++) {
  16.       for (int j = 1; j <= n2; j++) {
  17.         int replace = dp[i - 1][j - 1] + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1);
  18.         int delete = dp[i - 1][j] + 1;
  19.         int insert = dp[i][j - 1] + 1;
  20.         dp[i][j] = Math.min(replace, Math.min(delete, insert));
  21.       }
  22.     }
  24.     return dp[n1][n2];
  25.   }
  26. }